# -*- coding: UTF-8 -*-
from typing import List
from leetcode_helper import TestcaseHelper, SolutionBase


class Trie:
    L = 30

    def __init__(self):
        # left -> 0
        # right -> 1
        self.left = None
        self.right = None

    # 从数字的最高位开始构建，存放最大的数为10的9次 < 2的30次方
    def insert(self, value: int):
        node = self
        for i in range(self.L, -1, -1):
            bit = (value >> i) & 1
            if bit == 0:    # left node
                if not node.left:   # None node, create new one
                    node.left = Trie()
                node = node.left
            else:   # right node
                if not node.right:  # None node, create new one
                    node.right = Trie()
                node = node.right

    def get_max_xor(self, value: int) -> int:
        xor_value = 0
        node = self

        for i in range(self.L, -1, -1):
            bit = (value >> i) & 1
            hit = False
            if bit == 0:
                if node.right:
                    node = node.right
                    hit = True
                else:
                    node = node.left
            else:
                if node.left:
                    node = node.left
                    hit = True
                else:
                    node = node.right
            if hit:
                xor_value |= (1 << i)
        return xor_value


class Solution(SolutionBase):
    # 解题的方法，命名和Leetcode的保持一致即可

    # 考虑XOR操作，数的二进制排列有大量的0和1组合
    # 下面是baidu的解释
    # 字典输，单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。
    # 典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），
    # 所以经常被搜索引擎系统用于文本词频统计。
    # 它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

    def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        q = len(queries)
        n = len(nums)

        nums.sort()

        # 为了进一步优化查询的效率，如果查询的元素也是有序的，那么不需要完整构建Trie，然后再查询。
        # 只需要随着不断的查询来构建Trie， 所以需要对queries也要排序，同时记录每个查询的元素对应的index，这样好回填答案
        # 需要重新构建一个list，元素是x，m，i，其中i为答案的下标，按照m来排序
        new_queries = sorted([(x, m, i) for i, (x, m) in enumerate(queries)], key=lambda query: query[1])
        ans = [0] * q   # 预设好答案
        index = 0
        trie = Trie()

        for x, m, ans_index in new_queries:
            # 根据m构建Trie
            while index < n and nums[index] <= m:
                trie.insert(nums[index])
                index += 1

            # 通过x在Trie中查询
            if index > 0:
                # 设置答案
                ans[ans_index] = trie.get_max_xor(x)
            else:
                ans[ans_index] = -1

        return ans

    # 暴力解，超时，复杂度是O(n的平方)
    # 数据量n是10的5次方，复杂度超过10的10次方，大于10的8次方，肯定超时，不能用暴力解
    def maximizeXorForce(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        ans = []
        # 1-将nums排序
        nums.sort()

        # 2-遍历queries，针对每个xi，二分法找到在nums_sorted的index
        # O(n * n) > 10的10次方，肯定超时；所以应该考虑优化
        for x, m in queries:    # O(n)
            not_more_index = self.get_not_more_index(nums, m)   # O(logn)
            if not_more_index > -1:
                max_xor = self.get_max_xor(nums[0: not_more_index + 1], x)  # O(n)
                # 3-将nums_sorted中小于index的值与xi做个xor，得出最大值，保存
                ans.append(max_xor)
            else:
                ans.append(-1)

        return ans

    # O(logn)
    def get_not_more_index(self, nums, value):
        if value < nums[0]:
            return -1

        low = 0
        high = len(nums) - 1

        while low <= high:
            mid = (low + high) >> 1
            guess = nums[mid]
            if guess == value:
                return mid
            if guess > value:
                high = mid - 1
            else:
                low = mid + 1

        return low - 1

    # O(n)
    def get_max_xor(self, array, x):
        max_xor = 0
        for value in array:
            max_xor = max(x ^ value, max_xor)

        return max_xor

    # TODO: 在SolutionBase里实现了默认的checkResult，如果不适用与特殊题目，需要重写具体的实现
    # 检查结果是否正确的方法，不同的case，检查方法不同
    def check_result(self, expect, result) -> bool:
        return self.check_result_array(expect, result)



if __name__ == '__main__':
    solution = Solution()

    # 按照leetcode的题目说明，将基本的test case填入
    # 每条case的最后一个元素是正确的结果，即期待的结果
    testcases = [
        ([0, 1, 2, 3, 4], [[3, 1], [1, 3], [5, 6]], [3, 3, 7]),  # 使用元组来保存输入的数据，期待的结果
        ([5, 2, 4, 6, 6, 3], [[12, 4], [8, 1], [6, 3]], [15, -1, 5]),
        ([536870912, 0, 534710168, 330218644, 142254206],
         [[214004, 404207941]],
         [330170208])
    ]

    for case_item in testcases:
        # 获取测试用的case和期待的执行结果
        # TODO: 单独一条的Test case的组成随题目的不同而改变，需要按照题目来修改代码

        input1 = case_item[0]
        input2 = case_item[1]

        expect = case_item[len(case_item) - 1]
        # TODO: 调用对应方法，需要替换具体的方法
        exec_result = solution.maximizeXor(input1, input2)

        # 判断执行结果，输出提示信息
        check_result = solution.check_result(expect, exec_result)
        TestcaseHelper.print_case(check_result, case_item, exec_result)

